/* 376. 摆动序列 */
/**
 * @param {number[]} nums
 * @return {number}
 */

/* 
    动态规划 
    i       0       1       2       3       4       5   
    nums    1       7       4
    up      1       2       2
            [1]   [1,7]     [1,7]
    down    1       1       3
            [1]     [1]     [1,7,4]
*/
var wiggleMaxLength = function (nums) {
    const n = nums.length
    if (n < 2) return n
    /* 
        上升序列 
        up[i]:表示当前数摆动的最大序列
    */
    const up = new Array(n).fill(0)
    /* 下架序列 */
    const down = new Array(n).fill(0)
    up[0] = down[0] = 1
    for (let i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) {
            /* 它的上一个下降序列 + 1 */
            up[i] = Math.max(up[i - 1], down[i - 1] + 1)
            down[i] = down[i - 1]
        } else if (nums[i] < nums[i - 1]) {
            down[i] = Math.max(down[i - 1], up[i - 1] + 1)
            up[i] = up[i - 1]
        } else {
            up[i] = up[i - 1]
            down[i] = down[i - 1]
        }
    }

    return Math.max(up[n - 1], down[n - 1])
}
/* 动态规划 优化 */
var wiggleMaxLength = function (nums) {
    if (nums.length < 2) return nums.length
    let up = 1, down = 1
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            up = Math.max(up, down + 1)
        } else if (nums[i] < nums[i - 1]) {
            down = Math.max(down, up + 1)
        }
    }
    return Math.max(up, down)
};
/* 贪心 */
var wiggleMaxLength = function (nums) {
    const n = nums.length
    if (n < 2) return
    let prevDiff = nums[1] - nums[0]
    let ret = prevDiff !== 0 ? 2 : 1
    for (let i = 2; i < n; i++) {
        const diff = nums[i] - nums[i - 1]
        if ((diff > 0 && prevDiff <= 0) || (diff < 0) && prevDiff >= 0) {
            ret++
            prevDiff = diff
        }
    }
    return ret
}